#define _CRT_SECURE_NO_WARNINGS 1
#include <vector>
#include <iostream>
using namespace std;
class Solution {
public:
    int maxValue(vector<vector<int> >& grid)
    {
        vector<vector<int>> dp(2, vector<int>(grid[0].size() + 1, 0));
        for (int i = 0;i < grid.size();i++)
        {
            for (int j = 0;j < grid[i].size();j++)
            {
                dp[1][j + 1] = max(dp[0][j + 1], dp[1][j]) + grid[i][j];
            }
            for (auto& a : dp[1])
            {
                cerr << a << " ";
            }
            cerr << endl;
            swap(dp[0], dp[1]);
        }
        return dp[0][grid[0].size()];
    }
};